1. Field of the Invention
The present invention relates to electrical circuitry for storing data. More specifically, the present invention relates to a method and an apparatus for efficiently implementing a last-in first-out buffer for storing data items.
2. Related Art
Stacks are one of the most commonly used data structures in computer systems. Only random access memories (RAMs), and possibly FIFOs (first-in-first out buffers), are more frequently used.
A stack receives a data item during a “put” operation. During a “get” operation, the stack returns the data item that was most recently inserted into the stack. A stack data structure operates analogously to a stack of plates, in which the last plate entered onto the top of the stack is the first plate to be retrieved from the stack. Hence, stacks are also referred to as last-in first-out (LIFO) buffers.
A stack can be implemented using a RAM with a top-of-stack pointer. Because of the high integration densities of RAMs, such an implementation consumes very little area per data item. However, an input to a random access memory must drive a large number of lines, which creates at large load. This a disadvantage because driving the large load can increase cycle time and can consume a significant amount of energy.
A stack can also be implemented as a linear array of cells in which put operations cause items in the linear array to shift one direction, and get operations cause items in the linear array to shift in the other direction. Such an implementation may have a small cycle time, because communications are local, concurrent, and involve only small loads. A potential disadvantage of such an implementation is that the total energy consumption per put or get operation can still be quite high, because each put or get operation may cause all items in the array to move. Hence, a linear array-based implementation of the stack is not energy efficient. A second disadvantage is that the area for a linear-array implementation is likely larger than that of a RAM-based design.
What is needed is a method and an apparatus for implementing a stack without the above-described problems of a RAM-based implementation or a linear array-based implementation.